package 二叉树;



public class 前中后序遍历 {
    public static void main(String[] args) {
        TreeNode treeNode1 = new TreeNode(1);
        TreeNode treeNode2 = new TreeNode(2);
        TreeNode treeNode3 = new TreeNode(3);
        TreeNode treeNode4 = new TreeNode(4);
        treeNode1.setNode1(treeNode2);
        treeNode1.setNode2(treeNode3);
        treeNode2.setNode1(treeNode4);

        BinaryTree binaryTree = new BinaryTree();
        binaryTree.setRoot(treeNode1);

//        binaryTree.preOrder();
        binaryTree.indeixOrder();
//        binaryTree.suffixOrder();

        System.out.println("二叉树查找");
        TreeNode t1 = binaryTree.preOrderSearch(4);
        System.out.println("最终查找到的二叉树节点为：" + t1.getId());

        System.out.println("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~");
        TreeNode t2 = binaryTree.suffixOrderSearch(3);
        System.out.println("最终后序查找到的二叉树节点为：" + t2.getId());

        System.out.println("---------------------二叉树删除----------------------");
        binaryTree.preOrder();
        binaryTree.deleteNode(2);
        System.out.println("删除后：");
        binaryTree.preOrder(); // 1 2
    }
}

class BinaryTree {
    private TreeNode root;

    public void setRoot(TreeNode root) {
        this.root = root;
    }

    public void preOrder() {
        if (this.root != null) {
            this.root.preOrder();
        } else {
            System.out.println("当前二叉树为空，无法遍历");
        }
    }

    /*
        public void preOrder(TreeNode root) {
            if (root == null) {
                System.out.println("当前二叉树为空，无法遍历");
                return;
            }
            this.root.preOrder();
        }

     */
    public void indeixOrder() {
        if (this.root != null) {
            this.root.infixOrder();
        } else {
            System.out.println("当前二叉树为空，无法遍历");
        }
    }

    public void suffixOrder() {
        if (this.root != null) {
            this.root.suffixOrder();
        } else {
            System.out.println("当前二叉树为空，无法遍历");
        }
    }

    // 前中后序查找
    public TreeNode preOrderSearch(int id) {
        if (this.root == null) {
            System.out.println("当前二叉树为空，无法查找");
            return null;
        }
        return this.root.preOrderSearch(id);
    }

    public TreeNode middleOrderSearch(int id) {
        if (this.root == null) {
            System.out.println("当前二叉树为空，无法中序查找");
            return null;
        }
        return this.root.middleOrderSearch(id);
    }

    public TreeNode suffixOrderSearch(int id) {
        if (this.root == null) {
            System.out.println("当前二叉树为空，无法后序查找");
            return null;
        }
        return this.root.suffixOrderSearch(id);
    }

    public void deleteNode(int id){
        if (this.root != null) {
            if (this.root.getId() == id) {
                this.root = null;
            }else{
                this.root.delNode(id);
            }
        }else{
            System.out.println("二叉树为空，无法删除id节点"+id);
        }
    }
}

class TreeNode {
    private TreeNode node1;
    private TreeNode node2;
    private int id;

    public int getId() {
        return id;
    }

    @Override
    public String toString() {
        return "TreeNode{" +
                "id=" + id +
                '}';
    }

    public TreeNode(int id) {
        this.id = id;
    }

    public void setNode1(TreeNode node1) {
        this.node1 = node1;
    }

    public void setNode2(TreeNode node2) {
        this.node2 = node2;
    }

    public void preOrder() {
        System.out.println(this.toString());
        if (this.node1 != null) {
            this.node1.preOrder();
        }
        if (this.node2 != null) {
            this.node2.preOrder();
        }
    }

    public void infixOrder() {
        if (this.node1 != null) {
            this.node1.infixOrder();
        }
        System.out.println(this.toString());
        if (this.node2 != null) {
            this.node2.infixOrder();
        }
    }

    public void suffixOrder() {
        if (this.node1 != null) {
            this.node1.suffixOrder();
        }
        if (this.node2 != null) {
            this.node2.suffixOrder();
        }
        System.out.println(this.toString());
    }

    public TreeNode preOrderSearch(int id) {
        System.out.println("当前查找的节点为" + this.getId());
        if (this.id == id) {
            return this;
        }
        TreeNode resNode = null;
        if (this.node1 != null) {
            resNode = this.node1.preOrderSearch(id);
        }
        if (resNode != null) {
            return resNode;
        }
        if (this.node2 != null) {
            resNode = this.node2.preOrderSearch(id);
        }
        return resNode;
    }

    public TreeNode middleOrderSearch(int id) {
        TreeNode resNode = null;
        if (this.node1 != null) {
            resNode = this.node1.middleOrderSearch(id);
        }
        if (resNode != null) {
            return resNode;
        }
        if (this.id == id) {
            return this;
        }
        if (this.node2 != null) {
            resNode = this.node2.middleOrderSearch(id);
        }
        return resNode;
    }

    public TreeNode suffixOrderSearch(int id) {
        TreeNode resNode = null;
        if (this.node1 != null) {
            resNode = this.node1.suffixOrderSearch(id);
        }
        if (resNode != null) { // 注意这句话必须判断，若直接在上面返回，若为null，则无法获取到id，报空指针异常
            return resNode;
        }
        if (this.node2 != null) {
            resNode = this.node2.suffixOrderSearch(id);
        }
        if (resNode != null) {
            return resNode;
        }
        System.out.println("当前后序查找到的节点为" + this.getId());
        if (this.id == id) {
            return this;
        }
        return resNode;
    }

    public void delNode(int id) {
        if (this.node1 != null && this.node1.id == id) { // 先判断根节点左子节点
            this.node1 = null;
            return;
        }
        if (this.node1 != null) { // 再判断左子节点的孩子节点
            this.node1.delNode(id);
        }
        // 上下if语句顺序可以颠倒
        if (this.node2 != null && this.node2.id == id) { // 接着判断根节点右子节点
            this.node2 = null;
            return;
        }

        if (this.node2 != null) {
            this.node2.delNode(id);
        }
    }
}